package 热题100.图论.课程表_207_中等;

import java.util.Deque;
import java.util.LinkedList;

/*
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：
1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同

思路：
        将课程变为图，看是否是拓扑图，是的话就一定能学完，不是的话就说明有环就不能学完。
        如果需要将课程的顺序记录下来，就将count换成数组就行，或者手写队列更方便。
        1.初始化邻接表，指向空指针。
        2.将所有课程用邻接表形式变为图，并更新入度。
        3.遍历入度为0的点加入队列，队列中的课程是学的起点，因为没有课程指向它们。
        4.然后依次拿出队列中的课程，作为邻接矩阵的起点开始遍历，遍历到的课程将入度-1，如果入度为0，说明不需要学其他的了可以直接开始学该课程，就把该课程加入队列。
        5.如果加入队列的课程数等于总课程数，就表示是拓扑图。
* */
public class Solution {
    public static void main(String[] args) {
        int numCourses = 2;
        int[][] prerequisites = {{1, 0}, {0, 1}};
        System.out.println(canFinish(numCourses, prerequisites));
    }
    static int N = 5010, idx = 0;
    static int[] h = new int[N], d = new int[N]; // 邻接表,入度表
    static int[] e = new int[N], ne = new int[N]; // 课程的值和能学的下一个课程
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        int count = 0;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < numCourses; i ++){
            h[i] = -1; // 初始化邻接表
        }
        // 建立邻接表
        for (int[] t : prerequisites){
            int x = t[1], y = t[0];
            add(x, y);
            d[y] ++;
        }
        // 把一开始入度为0的课程加入队列
        for (int i = 0; i < numCourses; i ++){
            if (d[i] == 0){
                deque.offer(i);
            }
        }
        // 对课程进行遍历减少入度
        while (!deque.isEmpty()){
            int x = deque.poll();
            count ++;
            for (int i = h[x]; i != -1; i = ne[i]){
                int y = e[i]; // 拿y是为了减少入度,和加入队列
                d[y] --;
                if (d[y] == 0){
                    deque.offer(y);
                }
            }
        }

        return count == numCourses;
    }

    public static void add(int x, int y){
        e[idx] = y;
        ne[idx] = h[x];
        h[x] = idx ++;
    }
}
